class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        M = len(matrix)
        N = len(matrix[0])
        DP = [1 if matrix[0][j] == '1' else 0 for j in range(N)]
        max_len = max(DP)
        for i in range(1, M):
            for j in range(-1, - N - 1, -1):
                if j == - N:
                    DP[j] = 1 if matrix[i][j] == '1' else 0
                else:
                    if matrix[i][j] == '0':
                        DP[j] = 0
                    else:
                        if DP[j - 1] == 0:
                            DP[j] = 1
                        else:
                            one_side = 0
                            one_side_flag = True
                            other_side = 0
                            other_side_flag = True
                            for k in range(1, DP[j - 1] + 1):
                                if one_side_flag:
                                    if matrix[i][j - k] == '1':
                                        one_side += 1
                                    else:
                                        one_side_flag = False
                                else:
                                    break
                            for k in range(1, DP[j - 1] + 1):
                                if other_side_flag:
                                    if matrix[i - k][j] == '1':
                                        other_side += 1
                                    else:
                                        other_side_flag = False
                                else:
                                    break
                            DP[j] = 1 + min(DP[j - 1], one_side, other_side)
            max_len = max(max_len, max(DP))
        return max_len ** 2





data = Solution()
matrix = [["1", "0", "1", "1", "1"], ["1", "0", "1", "1", "1"], ["1", "1", "1", "1", "1"], ["1", "0", "0", "1", "0"]]
print(data.maximalSquare(matrix))
matrix = [["0","1"],["1","0"]]
print(data.maximalSquare(matrix))
matrix = [["0"]]
print(data.maximalSquare(matrix))